#include <assert.h>
#include <functional>
using namespace std;

/**
 * @brief 在[start, end]范围内搜最后一个0的位置，要保证区间存在
 * @param start  
 * @param end 
 * @param f f函数作用于[start, end]，保证前半段都是0，后半段都是1
 * @return int 返回最后一个算出0的位置，如果返回start-1说明全1
 */
int bsLast0(int start, int end, function<int(int)> f){
	assert(start <= end);
    int left = start, right = end, mid;
	do{
        mid = (left + right) >> 1;
		auto tmp = f(mid);
		assert(0 == tmp or 1 == tmp);
		if(tmp == 1) right = mid - 1;
		else left = mid + 1; 
	}while(left <= right);
	return right;
}

/**
 * @brief 在[start, end]范围内搜第一个1的位置，要保证区间存在
 * @param start  
 * @param end 
 * @param f f函数作用于[start, end]，保证前半段都是0，后半段都是1
 * @return int 返回第一个算出1的位置，如果返回end+1说明全零
 */
int bsFirst1(int start, int end, function<int(int)> f){
    assert(start <= end);
	int left = start, right = end, mid;
	do{
        mid = (left + right) >> 1;
		auto tmp = f(mid);
		assert(0 == tmp or 1 == tmp);
		if(tmp == 1) right = mid - 1;
		else left = mid + 1; 
	}while(left <= right);
	return left;
}

/**
 * IT是迭代器类型 
 * T是标定物类型
 * Cmp是函数类型，必须是function<bool(*IT, T)>
 * cmp是一个函数，所有[begin, end)范围内的东西
 * 前半段cmp(*it, anchor)都返回true，后半段都返回false
 * 返回第一个为false的迭代器
 */
template<typename IT, typename T, typename Cmp>
IT bsFirstFalse(IT begin, IT end, const T & anchor, Cmp cmp){
    return lower_bound(begin, end, anchor, cmp);
}

/**
 * IT是迭代器类型 
 * T是标定物类型
 * Cmp是函数类型，必须是function<bool(T, *IT)>
 * cmp是一个函数，所有[begin, end)范围内的东西
 * 前半段cmp(anchor, *it)都返回false，后半段都返回true
 * 返回第一个为true的迭代器
 */
template<typename IT, typename T, typename Cmp>
IT bsFirstTrue(IT begin, IT end, const T & anchor, Cmp cmp){
    return upper_bound(begin, end, anchor, cmp);
}